#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <windows.h>

#define MAX_VERTICES 100

/* 定义边的结构体 */
typedef struct
{
    int r1;
    int r2;
    int weight;
} Edge;

/* 比较函数，用于 qsort 排序 */
int compare(const void *a, const void *b)
{
    Edge *e1 = (Edge *)a;
    Edge *e2 = (Edge *)b;
    return e1->r1 - e2->r1;
}

/* Dijkstra 算法 */
void dijkstra(Edge *edges, int num_edges, int start)
{
    int dist[MAX_VERTICES];
    int visited[MAX_VERTICES];
    int prev[MAX_VERTICES];
    int num_vertices = 0;

    /* 找出最大顶点编号以确定顶点数 */
    for (int i = 0; i < num_edges; i++)
    {
        if (edges[i].r1 > num_vertices)
            num_vertices = edges[i].r1;
        if (edges[i].r2 > num_vertices)
            num_vertices = edges[i].r2;
    }
    num_vertices++;

    /* 初始化距离、访问和前驱数组 */
    for (int i = 0; i < num_vertices; i++)
    {
        dist[i] = INT_MAX;
        visited[i] = 0;
        prev[i] = -1;
    }
    dist[start] = 0;

    /* Dijkstra算法核心逻辑 */
    for (int count = 0; count < num_vertices - 1; count++)
    {
        int min_dist = INT_MAX, min_index;
        for (int v = 0; v < num_vertices; v++)
        {
            if (!visited[v] && dist[v] <= min_dist)
            {
                min_dist = dist[v];
                min_index = v;
            }
        }
        visited[min_index] = 1;
        for (int i = 0; i < num_edges; i++)
        {
            if (edges[i].r1 == min_index)
            {
                int v = edges[i].r2;
                int weight = edges[i].weight;
                if (!visited[v] && dist[min_index] != INT_MAX && dist[min_index] + weight < dist[v])
                {
                    dist[v] = dist[min_index] + weight;
                    prev[v] = min_index;
                }
            }
        }
    }

    /* 输出最短路径 */
    for (int i = 0; i < num_vertices; i++)
    {
        if (i != start)
        {
            printf("从 %d 到 %d 的最短路径: ", start, i);
            if (dist[i] == INT_MAX)
            {
                printf("不可达\n");
            }
            else
            {
                int current = i;
                while (current != -1)
                {
                    printf("%d ", current);
                    current = prev[current];
                }
                printf("\n");
            }
        }
    }
}

int main()
{
    SetConsoleOutputCP(65001);

    Edge edges[MAX_VERTICES];
    int num_edges = 0;

    /* 模拟输入图结构，格式为(r1,r2,weight) */
    edges[num_edges].r1 = 1;
    edges[num_edges].r2 = 2;
    edges[num_edges].weight = 1;
    num_edges++;

    edges[num_edges].r1 = 1;
    edges[num_edges].r2 = 3;
    edges[num_edges].weight = 4;
    num_edges++;

    edges[num_edges].r1 = 2;
    edges[num_edges].r2 = 3;
    edges[num_edges].weight = 2;
    num_edges++;

    edges[num_edges].r1 = 2;
    edges[num_edges].r2 = 4;
    edges[num_edges].weight = 5;
    num_edges++;

    edges[num_edges].r1 = 3;
    edges[num_edges].r2 = 4;
    edges[num_edges].weight = 1;
    num_edges++;

    /* 按 r1 排序边数组 */
    qsort(edges, num_edges, sizeof(Edge), compare);

    int start = 1; // 起始顶点
    dijkstra(edges, num_edges, start);

    return 0;
}